{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from numba import njit \n",
    "from collections import namedtuple\n",
    "import random\n",
    "import math\n",
    "from collections import namedtuple\n",
    "\n",
    "Point = namedtuple(\"Point\", ['x', 'y'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 499,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120.78088305266449"
      ]
     },
     "execution_count": 499,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.exponential(1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('tsp_5_1.txt') as input_data:\n",
    "#     lines = input_data.split('\\n')\n",
    "    lines= list(input_data)\n",
    "\n",
    "    nodeCount = int(lines[0])\n",
    "\n",
    "    points = []\n",
    "    for i in range(1, nodeCount+1):\n",
    "        line = lines[i]\n",
    "        parts = line.split()\n",
    "        points.append(Point(float(parts[0]), float(parts[1])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## greedy search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 4, 3, 2, 1]"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def length(point1, point2):\n",
    "    return math.sqrt((point1.x - point2.x)**2 + (point1.y - point2.y)**2)\n",
    "##a very pool greedy search\n",
    "solution_points=[points[i-1]]\n",
    "solution_index=[0]\n",
    "available_points=list(range(1,nodeCount))\n",
    "\n",
    "for position in range(1,nodeCount):\n",
    "    better_point= available_points[0]\n",
    "    dis= length(solution_points[position-1], points[better_point])\n",
    "    for k in available_points:\n",
    "        if length(solution_points[position-1], points[k])< dis:\n",
    "            better_point= k\n",
    "            dis=length(solution_points[position-1], points[k])\n",
    "    solution_index.append(better_point)\n",
    "    solution_points.append(points[better_point])\n",
    "    available_points.pop((better_point-1))\n",
    "\n",
    "\n",
    "solution_points\n",
    "solution_index    \n",
    "solution=solution_index           \n",
    "obj = length(points[solution[-1]], points[solution[0]])\n",
    "for index in range(0, nodeCount-1):\n",
    "    obj += length(points[solution[index]], points[solution[index+1]])\n",
    "\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2-opt local search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 162,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "##regular swap using list, instead of np.array\n",
    "def swap_dist(index_1, index_2, solution):\n",
    "    l= len(solution)\n",
    "    curr_dist=length(points[solution[((index_1-1)%l)]], points[solution[index_1]]) + length(points[solution[((index_2+1)%l)]], points[solution[index_2]])\n",
    "    swap_dist= length(points[solution[((index_1-1)%l)]], points[solution[index_2]]) + length(points[solution[((index_2+1)%l)]], points[solution[index_1]])\n",
    "    return swap_dist-curr_dist\n",
    "\n",
    "\n",
    "solution=list(range(nodeCount))\n",
    "for i in range(10):\n",
    "    for position in range(1,nodeCount):\n",
    "        curr_dist=0\n",
    "        best_point = solution[position]\n",
    "        original_point= solution[position]\n",
    "        best_index=position\n",
    "        for index in range(position+1, nodeCount):\n",
    "            if swap_dist(position, index, solution)<=curr_dist:\n",
    "                curr_dist= swap_dist(position, index, solution)\n",
    "                best_point= solution[index]\n",
    "                best_index=index\n",
    "        solution[position] = best_point\n",
    "        solution[best_index] = original_point\n",
    "\n",
    "# calculate the length of the tour\n",
    "obj = length(points[solution[-1]], points[solution[0]])\n",
    "for index in range(0, nodeCount-1):\n",
    "    obj += length(points[solution[index]], points[solution[index+1]])\n",
    "\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2-opt search using numba"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('tsp_5_1.txt') as input_data:\n",
    "#     lines = input_data.split('\\n')\n",
    "    lines= list(input_data)\n",
    "\n",
    "    nodeCount = int(lines[0])\n",
    "\n",
    "#     points = []\n",
    "#     for i in range(1, nodeCount+1):\n",
    "#         line = lines[i]\n",
    "#         parts = line.split()\n",
    "#         points.append(Point(float(parts[0]), float(parts[1])))\n",
    "\n",
    "    points_np=np.zeros((nodeCount,2))\n",
    "    for i in range(1, nodeCount+1):\n",
    "        line = lines[i]\n",
    "        parts = line.split()\n",
    "        points_np[i-1][0]= float(parts[0])\n",
    "        points_np[i-1][1]= float(parts[1])\n",
    "    \n",
    "    solution=np.zeros(nodeCount)\n",
    "    for i in range(nodeCount):\n",
    "        solution[i]=i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from numba import njit \n",
    "\n",
    "@njit(fastmath=True) \n",
    "def numba_swap(points_np, solution,nodeCount):\n",
    "    \n",
    "    ## 2-OPT swap local search:\n",
    "    for position in range(1,nodeCount):\n",
    "        curr_dist=0\n",
    "        best_point = solution[position]\n",
    "        original_point= solution[position]\n",
    "        best_index=position\n",
    "        for index in range(position+1, nodeCount):\n",
    "            if swap_dist(position, index, solution)<=curr_dist:\n",
    "                curr_dist= swap_dist(position, index, solution)\n",
    "                best_point= solution[index]\n",
    "                best_index=index\n",
    "        solution[position] = best_point\n",
    "        solution[best_index] = original_point\n",
    "    \n",
    "    return solution\n",
    "\n",
    "@njit(fastmath=True) \n",
    "def swap_dist(index_1, index_2, solution):\n",
    "    l= len(solution)\n",
    "    curr_dist=length(points_np[int(solution[((index_1-1)%l)])], points_np[int(solution[index_1])]) + length(points_np[int(solution[((index_2+1)%l)])], points_np[int(solution[index_2])]) \n",
    "    swap_dist= length(points_np[int(solution[((index_1-1)%l)])], points_np[int(solution[index_2])])  + length(points_np[int(solution[((index_2+1)%l)])], points_np[int(solution[index_1])])\n",
    "    return swap_dist-curr_dist\n",
    "    \n",
    "@njit(fastmath=True) \n",
    "def length(point1, point2):\n",
    "    return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 1, 2, 3, 4])"
      ]
     },
     "execution_count": 173,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for n in range(10):\n",
    "    solution= numba_swap(points_np, solution,nodeCount)\n",
    "    solution=solution.astype(int)\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2-opt search using numba and simulated annealing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 412,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('tsp_5_1.txt') as input_data:\n",
    "#     lines = input_data.split('\\n')\n",
    "    lines= list(input_data)\n",
    "\n",
    "    nodeCount = int(lines[0])\n",
    "    points_np=np.zeros((nodeCount,2))\n",
    "    for i in range(1, nodeCount+1):\n",
    "        line = lines[i]\n",
    "        parts = line.split()\n",
    "        points_np[i-1][0]= float(parts[0])\n",
    "        points_np[i-1][1]= float(parts[1])\n",
    "    \n",
    "    solution=np.zeros(nodeCount)\n",
    "    for i in range(nodeCount):\n",
    "        solution[i]=i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 493,
   "metadata": {},
   "outputs": [],
   "source": [
    "@njit(fastmath=True) \n",
    "def numba_swap(points_np, solution,nodeCount, t=1):\n",
    "    \n",
    "    ## 2-OPT swap local search:\n",
    "    for position in range(1,nodeCount):\n",
    "        curr_dist=0\n",
    "        best_point = solution[position]\n",
    "        original_point= solution[position]\n",
    "        best_index=position\n",
    "        for index in range(position+1, nodeCount):\n",
    "            if swap_dist(position, index, solution)<=curr_dist:\n",
    "                curr_dist= swap_dist(position, index, solution)\n",
    "                best_point= solution[index]\n",
    "                best_index=index\n",
    "            elif np.exp(-(swap_dist(position, index, solution)- curr_dist)/t)>=random.random():\n",
    "                best_point= solution[index]\n",
    "                best_index=index\n",
    "        solution[position] = best_point\n",
    "        solution[best_index] = original_point\n",
    "    \n",
    "    return solution\n",
    "\n",
    "@njit(fastmath=True) \n",
    "def swap_dist(index_1, index_2, solution):\n",
    "    l= len(solution)\n",
    "    index_low= min(index_1, index_2)\n",
    "    index_high=max(index_1, index_2)\n",
    "    curr_dist=length(points_np[int(solution[((index_low-1)%l)])], points_np[int(solution[index_low])]) + length(points_np[int(solution[((index_high+1)%l)])], points_np[int(solution[index_high])]) \n",
    "    swap_dist= length(points_np[int(solution[((index_low-1)%l)])], points_np[int(solution[index_high])])  + length(points_np[int(solution[((index_high+1)%l)])], points_np[int(solution[index_low])])\n",
    "    return swap_dist-curr_dist\n",
    "    \n",
    "@njit(fastmath=True) \n",
    "def length(point1, point2):\n",
    "    return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 492,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 492,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_obj=100000000000000000000\n",
    "\n",
    "for i in range(10):\n",
    "    for k in range(5):\n",
    "        solution= numba_swap(points_np, solution,nodeCount, (i*10+1)/500)\n",
    "        solution=solution.astype(int)\n",
    "        obj = length(points[solution[-1]], points[solution[0]])\n",
    "        for index in range(0, nodeCount-1):\n",
    "            obj += length(points[solution[index]], points[solution[index+1]])\n",
    "\n",
    "        if obj<=best_obj:\n",
    "            best_solution=[]\n",
    "            for point_index in solution:\n",
    "                best_solution.append(point_index)\n",
    "    \n",
    "\n",
    "# solution\n",
    "best_solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "best_obj=100000000000000000000\n",
    "best_solution=[]\n",
    "for i in range(10):\n",
    "    for k in range(3):\n",
    "        solution= numba_swap(points_np, solution,nodeCount, (i*8+1)/100) ### SA\n",
    "        solution=solution.astype(int)\n",
    "        obj = length_obj(points[solution[-1]], points[solution[0]])\n",
    "        for index in range(0, nodeCount-1):\n",
    "            obj += length_obj(points[solution[index]], points[solution[index+1]])\n",
    "\n",
    "        if obj<=best_obj:\n",
    "            best_solution=[]\n",
    "            for point_index in solution:\n",
    "                best_solution.append(point_index)\n",
    "\n",
    "n=0\n",
    "while n>2:\n",
    "    solution= numba_swap(points_np, solution,nodeCount)\n",
    "    solution=solution.astype(int)\n",
    "    obj = length_obj(points[solution[-1]], points[solution[0]])\n",
    "    for index in range(0, nodeCount-1):\n",
    "        obj += length_obj(points[solution[index]], points[solution[index+1]])\n",
    "\n",
    "    if obj<=best_obj:\n",
    "        best_solution=[]\n",
    "        for point_index in solution:\n",
    "            best_solution.append(point_index)\n",
    "    else:\n",
    "        n+=1\n",
    "\n",
    "solution= best_solution\n",
    "# calculate the length of the tour\n",
    "obj = length(points_np[int(solution[-1])], points_np[int(solution[0])])\n",
    "for index in range(0, nodeCount-1):\n",
    "    obj += length(points_np[int(solution[index])], points_np[int(solution[index+1])])\n",
    "    \n",
    "best_solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 308,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.0"
      ]
     },
     "execution_count": 308,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "obj = length(points[solution[-1]], points[solution[0]])\n",
    "for index in range(0, nodeCount-1):\n",
    "    obj += length(points[solution[index]], points[solution[index+1]])\n",
    "    \n",
    "obj"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
